//    Copyright (C) Kherty.  All rights reserved.
using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Text;

namespace OpenLS.Spreadsheet
{
    internal sealed class IntervalManager
    {
        internal struct IntervalBounds
        {
            private readonly int _length;
            private readonly int _firstIndex;

            public IntervalBounds(int firstIndex, int length)
            {
                Contract.Requires(firstIndex >= 0);
                Contract.Requires(length > 0);
                _firstIndex = firstIndex;
                _length = length;
            }

            public int Length
            {
                get { return _length; }
            }

            public int FirstIndex
            {
                get { return _firstIndex; }
            }

            public int LastIndex
            {
                get { return FirstIndex + Length - 1; }
            }

            public int NextIndex
            {
                get { return FirstIndex + Length; }
            }

            public bool Equals(IntervalBounds bounds)
            {
                return Length == bounds.Length && FirstIndex == bounds.FirstIndex;
            }

            public IntervalBounds RestrictedFirst(int i)
            {
                if (i < FirstIndex)
                    return this;
                int length = Length + FirstIndex - i;
                int firstIndex = i;
                return new IntervalBounds(firstIndex, length);
            }

            public IntervalBounds RestrictedNext(int nextIndex)
            {
                int maxLength = nextIndex - FirstIndex;
                int length = Math.Min(Length, maxLength);
                return new IntervalBounds(FirstIndex, length);
            }


            public bool Contains(int index)
            {
                if (FirstIndex > index)
                    return false;
                if (FirstIndex + Length <= index)
                    return false;
                return true;
            }


            public override string ToString()
            {
                return string.Format("[{0},{1}]", FirstIndex, LastIndex);
            }
        }

        private sealed class InternalItem
        {
            private readonly IntervalManager _manager;
            private double _offset;

            public InternalItem(IntervalManager manager, IntervalBounds position, double itemLength)
            {
                _manager = manager;
                Contract.Requires(itemLength >= 0);
                ItemLength = itemLength;
                Bounds = position;
            }

            public double ItemLength { get; set; }
            public IntervalBounds Bounds { get; set; }

            public double Offset
            {
                get
                {
                    _manager.ensureOffsets();
                    return _offset;
                }
                set { _offset = value; }
            }

            public override string ToString()
            {
                return string.Format("{0}({1})<{2}>", Bounds, ItemLength, GetHashCode());
            }
        }

        public override string ToString()
        {
            var result = new StringBuilder();
            foreach (InternalItem list in _items)
            {
                result.Append(list.ToString());
            }
            for (int i = 0; i < 10; i++)
                result.Append("," + OffsetAt(i));
            return string.Format("{0}{{{1}}}", result, GetHashCode());
        }

        public IntervalManager(double itemLength)
        {
            ItemLength = itemLength;
        }

        sealed class InternalItemList:List<InternalItem>
        {
            public InternalItem ItemForOffset(double offset)
            {
                return this[0];
            }
        }

        internal double ItemLength { get; private set; }
        private readonly InternalItemList _items = new InternalItemList();
        bool insertItem (int index, InternalItem item)
        {
            Contract.Assert((item != null));
            if (item.ItemLength == ItemLength)
                return false;
            if (index > 0 )
            {
                var previousItem = _items[index - 1];
                if (previousItem.Bounds.NextIndex == item.Bounds.FirstIndex)
                {
                    if (previousItem.ItemLength == item.ItemLength)
                    {
                        previousItem.Bounds = new IntervalBounds(previousItem.Bounds.FirstIndex, previousItem.Bounds.Length + item.Bounds.Length);
                        return false;
                    }
                }
            }
            _items.Insert(index, item);
            return true;
        }

        public void Set(IntervalBounds bounds, double value)
        {
            _consistent = false;
            var item = new InternalItem(this, bounds, value);
            int previousIndex = intervalIndex(bounds.FirstIndex);
            int nextIndex = intervalIndex(bounds.LastIndex);
            Contract.Assert(nextIndex >= previousIndex);
            switch (nextIndex - previousIndex)
            {
                case 0:
                    {
                        if (previousIndex == -1)
                        {
                            insertItem(0, item);
                            _consistent = false;
                            return;
                        }
                        InternalItem previousItem2 = _items[previousIndex];
                        if (previousItem2.Bounds.Equals(bounds))
                        {
                            previousItem2.ItemLength = value;
                            _consistent = false;
                            return;
                        }

                        if (bounds.LastIndex >= previousItem2.Bounds.LastIndex)
                        {
                            previousItem2.Bounds = previousItem2.Bounds.RestrictedNext(bounds.FirstIndex);
                            insertItem(previousIndex + 1, item);
                            _consistent = false;


                            return;
                        }

                        if (previousItem2.Bounds.FirstIndex == bounds.FirstIndex)
                        {
                            // previous is next
                            previousItem2.Bounds = previousItem2.Bounds.RestrictedFirst(bounds.NextIndex);
                            insertItem(previousIndex, item);
                            _consistent = false;

                            return;
                        }
#if SUPERDEBUG
                        Contract.Assert(ordered());
#endif
                        int previousNextIndex = previousItem2.Bounds.NextIndex;
                        previousItem2.Bounds = previousItem2.Bounds.RestrictedNext(bounds.FirstIndex);
#if SUPERDEBUG
                        Contract.Assert(ordered());
#endif
                        bool itemInserted = insertItem(previousIndex + 1, item);
#if SUPERDEBUG
                        Contract.Assert(ordered());
#endif
                        var newItem = new IntervalBounds(bounds.NextIndex,
                                                         previousNextIndex -
                                                         bounds.NextIndex);
                        var newInternalItem = new InternalItem(this, newItem, previousItem2.ItemLength);
                        insertItem(itemInserted ? previousIndex + 2 : previousIndex + 1, 
                                      newInternalItem);
#if SUPERDEBUG
                        Contract.Assert(ordered());
#endif
                        _consistent = false;

                        return;
                    }
                case 1:
                    {
                        InternalItem previousItem2 = _items[previousIndex];
                        InternalItem nextItem2 = _items[nextIndex];
                        previousItem2.Bounds = previousItem2.Bounds.RestrictedNext(bounds.FirstIndex);
                        nextItem2.Bounds = nextItem2.Bounds.RestrictedFirst(bounds.NextIndex);
                        insertItem(previousIndex + 1, item);
                        _consistent = false;
                        return;
                    }
                default:

                    InternalItem previousItem3 = _items[previousIndex];
                    InternalItem nextItem3 = _items[nextIndex];
                    for (int i = nextIndex - 1; i > previousIndex; i--)
                    {
                        _items.RemoveAt(i);
                    }
                    previousItem3.Bounds = previousItem3.Bounds.RestrictedNext(bounds.FirstIndex);
                    nextItem3.Bounds = nextItem3.Bounds.RestrictedFirst(bounds.NextIndex);
                    insertItem(previousIndex + 1, item);
                    _consistent = false;
                    break;
            }
        }

#if SUPERDEBUG
        [ContractInvariantMethod]
// ReSharper disable UnusedMember.Global
        protected void ObjectInvariant()
// ReSharper restore UnusedMember.Global
        {
            Contract.Invariant(ordered());
            Contract.Invariant(validLengths());
        }

        private bool validLengths()
        {
            for (int i = 0; i < _items.Count - 1; i++)
            {
                bool ok = _items[i].Bounds.FirstIndex + _items[i].Bounds.Length <= _items[i + 1].Bounds.FirstIndex;
                Contract.Assert(ok);
                if (!ok)
                    return false;
            }
            return true;
        }

        private bool ordered()
        {
            for (int i = 0; i < _items.Count - 1; i++)
            {
                if (!(_items[i].Bounds.FirstIndex < _items[i + 1].Bounds.FirstIndex))
                {
                //    Debug.WriteLine(string.Format("IntervalManager not ordered {0}<{1}", _items[i].Bounds.FirstIndex,
                  //                                _items[i + 1].Bounds.FirstIndex));
                  //  Debug.WriteLine(StringEnumerable.Concat(_items, "  "));
                }
                Contract.Assert(_items[i].Bounds.FirstIndex < _items[i + 1].Bounds.FirstIndex);
                if (!(_items[i].Bounds.FirstIndex < _items[i + 1].Bounds.FirstIndex))
                {
                    return false;
                }
            }
            return true;
        }
#endif

        public double OffsetAt(int index)
        {
            InternalItem it = internalItemAt(index);
            if (it == null)
            {
                return  ItemLength*(index);
            }
            int length = index - it.Bounds.FirstIndex;
            Contract.Assert(length >= 0);
            if (length < it.Bounds.Length)
            {
                return it.Offset + it.ItemLength*(length);
            }
            length = length - it.Bounds.Length;
            return it.Offset + it.ItemLength*it.Bounds.Length + ItemLength*length;
        }
        public double LengthAt (int index)
        {
            InternalItem it = internalItemAt(index);
            if (it == null)
            {
                return ItemLength ;
            }
            return it.ItemLength;
        }

        private int intervalIndex(int index)
        {
            Contract.Requires(index >= 0);
            Contract.Ensures(Contract.Result<int>() == -1 || Contract.Result<int>() >= _items.Count - 1 ||
                             _items[Contract.Result<int>() + 1].Bounds.FirstIndex > index);
            if (_items.Count == 0)
                return -1;
            int first = 0;
            int last = _items.Count - 1;
            InternalItem firstInterval = _items[first];
            if (firstInterval.Bounds.FirstIndex > index)
                return -1;
            if (firstInterval.Bounds.Contains(index))
                return first;
            InternalItem lastInterval = _items[last];
            while (last > first + 1)
            {
                if (firstInterval.Bounds.Contains(index))
                    return first;
                if (lastInterval.Bounds.Contains(index))
                    return last;
                int newIndex = (first + last)/2;
                InternalItem newInterval = _items[newIndex];
                if (newInterval.Bounds.Contains(index))
                    return newIndex;
                if (newInterval.Bounds.FirstIndex > index)
                {
                    last = newIndex;
                    lastInterval = newInterval;
                }
                else
                {
                    first = newIndex;
                    firstInterval = newInterval;
                }
            }
            if (lastInterval.Bounds.FirstIndex <= index)
                return last;
            return first;
        }

        private InternalItem internalItemAt(int index)
        {
            int i = intervalIndex(index);
            if (i < _items.Count - 1)
                Contract.Assert(_items[i + 1].Bounds.FirstIndex > index);
            if (i < 0)
            {
                return null;
            }
            return _items[i];
        }

        private bool _consistent;

        private void ensureOffsets()
        {
            if (_consistent)
                return;
            double currentOffset = 0;
            int lastIndex = 0;
            foreach (InternalItem item in _items)
            {
                currentOffset += (item.Bounds.FirstIndex - lastIndex)*ItemLength;
                item.Offset = currentOffset;
                currentOffset += item.Bounds.Length*item.ItemLength;
                lastIndex = item.Bounds.NextIndex;
            }
            _consistent = true;
        }

        
    }
}